//
// Created by Administrator on 2022/11/20.
// 分成小于等于区和大于区,以数组最后一个数为基准
//
#include "arrUtil.h"
#include <vector>

using namespace std;

int part(vector<int> &v, int l, int r)
///
/// \param v 数组
/// \param l 要分区的左索引
/// \param r 要分区的右索引
/// \return
{
    int less = l - 1;
    int i = l;
    int value = v[r];
    while (i <= r)
    {
        if (v[i] <= value)
        {
            swapVector(v, i, ++less);
//            printf("swap %d %d\n", i, less);
//            printVector(v);
        }
        i++;
    }
//    printf("less= %d\n", less);
    return less;
}

void quickSort(vector<int> &v, int L, int R)
{
    if (L<R)
    {
        int mid = part(v,L,R);
        quickSort(v,L,mid-1);
        quickSort(v,mid+1,R);
    }

}

int main()
{
    vector<int> arr = {7, 2, 9, 3, 6, 3, 6, 0};
    randVector(arr, 100);
//    arr = {7, 2, 9, 3, 6, 8};
//    part(arr, 0, arr.size() - 1);
    quickSort(arr,0,arr.size()-1);
    printf("%d\n",checkSortVector(arr));
    printVector(arr);
    return 0;
}
